
// 快速排序的原则就是找到基准元素后，大的放右边，小的放左边，这是基本原则，
// 满足这个原则就可以，那么实现方式上面就是会有多种方式

//简易 分块法  利用api的便利
var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};
    

// 交换法（没有开辟新的内存，算是比较好的） https://zhuanlan.zhihu.com/p/508663114
function sort(arr, startIndex, endIndex) {
    // 递归结束条件：startIndex大于等于endIndex的时候
    if (startIndex >= endIndex) {
        return;
    }
    // 得到基准元素的位置
    let pivotIndex = partition(arr, startIndex, endIndex);
    sort(arr, startIndex, pivotIndex - 1);
    sort(arr, pivotIndex + 1, endIndex);
}

function partition(arr, startIndex, endIndex) {
    // 选择第一个位置的元素作为基准元素
    let pivot = arr[startIndex];
    let left = startIndex;
    let right = endIndex;
    let index = startIndex;

    // 外循环在左右指针重合或者交错的时候结束
    while (right > left) {
        // right指针从右向左进行比较
        while (right > left) {
            if (arr[right] < pivot) {
                arr[left] = arr[right];
                index = right;
                left++;
                break;
            }
            right--;
        }
        // left指针从左向右进行比较
        while (right > left) {
            if (arr[left] > pivot) {
                arr[right] = arr[left];
                index = left;
                right--;
                break;
            }
            left++;
        }
    }
    arr[index] = pivot;
    return index;
}

let arr = [4, 5, 8, 1, 7, 2, 6, 3];
sort(arr, 0, arr.length - 1);
console.log(arr);


// 方法3
const quickSort = (array) => {
    const sort = (arr, left = 0, right = arr.length - 1) => {
     if (left >= right) {//如果左边的索引大于等于右边的索引说明整理完毕
      return
     }
    let i = left
    let j = right
    const baseVal = arr[j] // 取无序数组最后一个数为基准值
    while (i < j) {//把所有比基准值小的数放在左边大的数放在右边
     while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
      i++
     }
     arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
     while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
      j--
    }
     arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
    }
    arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
    sort(arr, left, j-1) // 将左边的无序数组重复上面的操作
    sort(arr, j+1, right) // 将右边的无序数组重复上面的操作
    }
    const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
    sort(newArr)
    return newArr
   }
    
   // 方法二：
   let _quickSort = (left, right, nums) => {
     let swap = (left, right, nums) => {
       let temp = nums[left]
       nums[left] = nums[right]
       nums[right] = temp
     }
     if (left <= right) {
       let val = nums[left]
       let [i, j] = [left, right]
    
       while (i < j) {
         while (i < j && nums[j] > val) {
           j--
         }
         while (i < j && nums[i] < val) {
           i++
         }
         if (i < j) {
           swap(i, j , nums)
         }
       }
       nums[i] = val
       _quickSort(left, i - 1, nums)
       _quickSort(i + 1, right, nums)
     }
   }
    
   let quickSort = (...numbers) => {
     _quickSort(0, numbers.length - 1, numbers)
     return numbers
   }
    
   console.log(quickSort(1, 20, 9, 13, 59, 19, 98))